The present invention relates to a buffer storage control technique, and, more particularly, to a buffer storage control apparatus and a buffer storage control method which are suitable for improving performance of an information processing system with storage hierarchy.
The relationships between access speed and cost, and between access speed and storage capacity, are important factors relating to the characteristics of a storage unit. It is generally known that the higher the operating speed of a storage unit, the higher the cost of this unit and that the lower the operating speed by a storage unit, the larger the storage capacity of the unit.
Therefore, in constructing a main storage of a relatively large capacity in an information processing system, such as a general purpose computer, for example, there is a limit to a realizable access speed because of the cost of the storage unit. As a result, a difference occurs in the access speed between a register storage of an extremely high operating speed within a central processing unit and the main storage. In this state, the operating speed of the central processing unit is restricted by the operating speed of the main storage.
On the other hand, because of the known characteristic of reference locality, there is a limit to the range of data that is accessed at one point of time among the total data that is stored in a large capacity main storage. Generally, the above problem is avoided by using the advantage of this characteristic to form a storage hierarchy in such a way that a buffer storage, the capacity of which is smaller than that of a main storage but the operating speed of which is higher than that of the main storage and is close to the operation speed of a central processing unit, is provided between the main storage and the central processing unit. Further, a data to which access is estimated to be made is copied in advance from the main storage to the buffer storage; and a higher buffer storage is accessible to the central processing unit.
In a storage hierarchy as described above, increasing the capacity of the buffer storage is advantageous in improving the performance of the central processing unit in that the probability that data required by the central processing unit exists in the buffer storage, or the hit ratio is increased. Also, the frequency of a low speed direct access to the main storage which takes time is reduced so that the instruction execution time in the central processing unit is reduced.
As one of method for making access from the central processing unit to the buffer storage, there is a so-called set-associative mapping method according to which a buffer storage is addressed with a few bits of a part of a logical address to thereby increase the speed of making an access to this buffer. In this method, however, in order to achieve the increase in the buffer storage capacity as described above, it is necessary to either (1) increase an address range for making access to the buffer storage (that is, number of columns which constitute the buffer storage) or (2) enhance the set associative mapping capability (that is, number of rows which belong to each column).
However, when the set associative mapping capability is improved, the frequency of comparison for checking all the rows which belong to the same column increases; So, there is a limit to the increase in the number of rows from the constraint of the cost due to the increase in the physical quantity of hardware.
In the information processing system which uses a virtual storage system, when the buffer storage capacity is increased, it becomes necessary that the address range for making access to the buffer address array, which stores a part of the logical address and a real address of the buffer storage by corresponding to each other, is expanded to a page address portion which needs a virtual-to-real address translation. Address translator only occurs in excess of the address portion within a page in which translation of the logical address is not necessary. In other words, since the buffer storage is managed by the real address, in order to make an access to the buffer address array with the real address, it is necessary to use a procedure for obtaining a real address from the logical address by using an address translator. Thus, problem of increasing a redundant time (overhead) from the point at which the logical address of a target data is established to the point at which the buffer storage is accessed.
Therefore, it has been a conventional practice to access a buffer address array in the form of a logical address in order to increase the capacity of a buffer storage.
When accessing of a buffer address array with a logical address, the access address used is comprised of 1.) (N: a positive integer) of a part of the page address portion; and, 2.) the address portion within the page. Since a logical address is different from a real address at the page address portion, it becomes possible that a certain real address is entered in 2.sup.N entries (classes) of the buffer address array. When the real address which has been obtained from accessing the buffer address array by using 1.) the N bits of the page address portion and 2. ) the address portion within the page which matches the real address which has been obtained from an address translation means, it is judged that the target data exists in the buffer storage (this is referred to as "logical hit").
On the other hand, in the case of no logical hit, it is necessary to make access to other classes of the buffer address array and decide whether there is a real address which matches with the real address in the other classes (this is referred to as "real hit") or there is no real address which matches the real address in the other classes (this is referred to as a not-in-buffer storage which is hereinafter abbreviated as "NIBS").
There are some examples of methods of detecting a real hit as follows.
(1) When there is no logical hit, the N bits of the page address portion are sequentially changed to make access to the buffer address array, and it is determined whether the obtained real address is matched with the target address or not. According to this method, it takes a long time to detect a real address when there are many classes. As a countermeasure for this, the time required for detecting a real address is reduced by providing a tag storage which is accessed by a real address and has information as to presence or absence of data of the real address in the buffer storage, as disclosed in the Japanese Patent Laid-Open JP-A-6280742, for example.
(2) All the classes of the buffer address array are read out simultaneously by using the address portion within the page, and judgement is made about the case of a real address whether it is a logical hit, a real hit, a not-in-buffer storage. In this case, since it is necessary to compare real addresses of all the classes, the probability is high that the time required for the detection will become long as compared with the time required for detecting logical hit only.
According to the above-described prior art techniques, there is a problem in all cases in that a increased time is required to detect real hit when there is no logical hit in accessing the buffer storage.
In other words, in the case of the abovedescribed prior art method (1), it is necessary to make access to all the other classes of the buffer address array in order to detect a real hit. It is also necessary to make access by a maximum 2.sup.N -1 times when the page address used for making access to the buffer address array has N bits. In the case where a tag storage is introduced to reduce the number of access times, it becomes necessary to make access to all the other classes of the buffer address array only when the tag storage is hit, of which the probability is small. However, since it is necessary to make access to the tag storage with a real address, it becomes essential that the real address is obtained from an address translation means. As a result, it becomes necessary to take additional time by the time required for making access to the tag storage in comparison with the case where there exists logical hit.
Further, in the case of the above-described prior art method (2), it is necessary to make access to all the classes of the buffer address array and use a comparing means is necessary to compare real addresses of all the classes. Therefore, for example, when a logical hit detecting means is separated from a real hit detecting means because of constraints in mounting these means, the real hit detecting time is extremely slow compared with a logical hit detecting time. In this case, additional time is necessary for making access to the buffer storage when there is no logical hit, which may increase the time for executing an instruction in the central processing unit.